use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

struct Solution;

impl Solution {
    fn rob(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if root.is_some() {
            let (exclude, include) = Solution::rob_sub(root);
            return i32::max(exclude, include);
        }
        0
    }

    fn rob_sub(root: Option<Rc<RefCell<TreeNode>>>) -> (i32, i32) {
        if let Some(root_rc) = root {
            let (exclude_left, include_left) = Solution::rob_sub(root_rc.borrow().left.clone());
            let (exclude_right, include_right) = Solution::rob_sub(root_rc.borrow().right.clone());

            return (
                // exclude self
                i32::max(exclude_left, include_left) + i32::max(exclude_right, include_right),
                // include self
                root_rc.borrow().val + exclude_left + exclude_right
            );
        }
        (0, 0)
    }
}

fn main() {
    Solution::rob(None);
}

